翻訳と辞書 Words near each other ・ Subgiant (band) ・ Subglacial channel ・ Subglacial eruption ・ Subglacial lake ・ Subglacial mound ・ Subglacial stream ・ Subglacial volcano ・ Subglottic stenosis ・ Subglottis ・ Subgoal labeling ・ Subgrade ・ Subgradient method ・ Subgrain rotation recrystallization ・ Subgranular zone ・ Subgraph ・ Subgraph isomorphism problem ・ Subgroup ・ Subgroup analysis ・ Subgroup growth ・ Subgroup method ・ Subgroup series ・ Subgroup test ・ Subgrouping ・ Subgroups of Amish ・ Subgroups of cyclic groups ・ Subgum ・ Subh (sultana) ・ Subh Sukh Chain ・ Subh-e-Pakistan ・ Subh-i-Azal Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Subgraph isomorphism problem ： ウィキペディア英語版 Subgraph isomorphism problem In theoretical computer science, the subgraph isomorphism problem is a computational task in which two graphs ''G'' and ''H'' are given as input, and one must determine whether ''G'' contains a subgraph that is isomorphic to ''H''. Subgraph isomorphism is a generalization of both the maximum clique problem and the problem of testing whether a graph contains a Hamiltonian cycle, and is therefore NP-complete.〔The original paper that proves the Cook–Levin theorem already showed subgraph isomorphism to be NP-complete, using a reduction from 3-SAT involving cliques.〕 However certain other cases of subgraph isomorphism may be solved in polynomial time.〔 Sometimes the name subgraph matching is also used for the same problem. This name puts emphasis on finding such a subgraph as opposed to the bare decision problem. ==Decision problem and computational complexity== To prove subgraph isomorphism is NP-complete, it must be formulated as a decision problem. The input to the decision problem is a pair of graphs ''G'' and ''H''. The answer to the problem is positive if ''H'' is isomorphic to a subgraph of ''G'', and negative otherwise. Formal question: Let $G=(V,E)$, $H=(V^\backslash prime,E^\backslash prime)$ be graphs. Is there a subgraph $G\_0=(V\_0,E\_0):\; V\_0\backslash subseteq\; V,\; E\_0\backslash subseteq\; E\backslash cap(V\_0\backslash times\; V\_0)$ such that $G\_0\backslash cong\; H$? I.e., does there exist an $f\backslash colon\; V\_0\backslash rightarrow\; V^\backslash prime$ such that $(v\_1,v\_2)\backslash in\; E\_0\backslash Leftrightarrow\; (f(v\_1),f(v\_2))\backslash in\; E^\backslash prime$? The proof of subgraph isomorphism being NP-complete is simple and based on reduction of the clique problem, an NP-complete decision problem in which the input is a single graph ''G'' and a number ''k'', and the question is whether ''G'' contains a complete subgraph with ''k'' vertices. To translate this to a subgraph isomorphism problem, simply let ''H'' be the complete graph ''K''''k''; then the answer to the subgraph isomorphism problem for ''G'' and ''H'' is equal to the answer to the clique problem for ''G'' and ''k''. Since the clique problem is NP-complete, this polynomial-time many-one reduction shows that subgraph isomorphism is also NP-complete.〔.〕 An alternative reduction from the Hamiltonian cycle problem translates a graph ''G'' which is to be tested for Hamiltonicity into the pair of graphs ''G'' and ''H'', where ''H'' is a cycle having the same number of vertices as ''G''. Because the Hamiltonian cycle problem is NP-complete even for planar graphs, this shows that subgraph isomorphism remains NP-complete even in the planar case. Subgraph isomorphism is a generalization of the graph isomorphism problem, which asks whether ''G'' is isomorphic to ''H'': the answer to the graph isomorphism problem is true if and only if ''G'' and ''H'' both have the same numbers of vertices and edges and the subgraph isomorphism problem for ''G'' and ''H'' is true. However the complexity-theoretic status of graph isomorphism remains an open question. In the context of the Aanderaa–Karp–Rosenberg conjecture on the query complexity of monotone graph properties, showed that any subgraph isomorphism problem has query complexity Ω(''n''3/2); that is, solving the subgraph isomorphism requires an algorithm to check the presence or absence in the input of Ω(''n''3/2) different edges in the graph.〔Here Ω invokes Big Omega notation.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Subgraph isomorphism problem」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.